package cn.mayday.algorithms.year2021.month1.C滑动窗口其实即使双指针;

import java.util.ArrayList;
import java.util.List;

/**
 * [简单]
 * <p>
 * 剑指 Offer 57 - II. 和为s的连续正数序列
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 * <p>
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 *
 * @description: TODO
 * @author: mayday
 * @date: 2021/5/14 8:14
 * @version: 1.0
 */
public class Offer057FindContinuousSequence {

    public static void main(String[] args) {

    }

    public int[][] findContinuousSequence(int target) {

        int left = 1; // 滑动窗口左边
        int right = 1; // 滑动窗口右边
        int sum = 0; // 记录初始值
        List<int[]> result = new ArrayList<>();// 因为不清楚有多少组结果，因此这边先用数组替代


        while (left < target / 2) { // 注意，一半时已经最大了。不需要遍历过去

            if (sum < target) { // 如果总值小于目标值，算上当前滑动串口右边值，窗口右边界右移
                sum = sum + right;
                right++;
            } else if (sum > target) { // 如果总值大于目标值，去掉当前滑动串口左边值，窗口左边界右移
                sum = sum - left;
                left++;
            } else { // 相等，找到了
                int[] tempResult = new int[right - left];
                for (int kk = left; kk < right; kk++) {
                    tempResult[kk - left] = kk;
                }
                result.add(tempResult);
            }
        }
        // List转数组，按照指定数组大小
        return result.toArray(new int[result.size()][]);
    }
}
